package leetcode.editor.cn.dsa05_annularLinkedList;
//给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//
// 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，po
//s 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 
//
// 说明：不允许修改给定的链表。 
//
// 进阶：
// 你是否可以使用 O(1) 空间解决此题？ 
//
//
// 示例 1：
//输入：head = [3,2,0,-4], pos = 1
//输出：返回索引为 1 的链表节点
//解释：链表中有一个环，其尾部连接到第二个节点。
// 
//
// 示例 2：
//输入：head = [1,2], pos = 0
//输出：返回索引为 0 的链表节点
//解释：链表中有一个环，其尾部连接到第一个节点。
// 
//
// 示例 3：
//输入：head = [1], pos = -1
//输出：返回 null
//解释：链表中没有环。
//
// 提示：
// 链表中节点的数目范围在范围 [0, 104] 内 
// -105 <= Node.val <= 105 
// pos 的值为 -1 或者链表中的一个有效索引 
// 
// Related Topics 链表 双指针 
// 👍 773 👎 0


public class LinkedListCycleIi142 {
    class ListNode {
        int val;
        ListNode next;
        ListNode (int x) {
            val = x;
            next = null;
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 因为题目中明确规定了节点值的范围：-10^5 <= Node.val <= 10^5
         * 因此我们可以使用标记值法：
         * 对节点进行遍历，每访问一个节点就进行标记，把值修改为非法值
         * 每次访问先判断该节点值是否非法，非法则表示有环，返回当前节点
         * @param head
         * @return
         */
        public ListNode detectCycle(ListNode head) {
            // 遍历链表的每一个节点
            while (head != null) {
                // 只要节点值非法，代表访问到了环的起点
                if (head.val == 100001) {
                    return head;
                }
                // 对节点进行标记，把节点值修改为非法值
                head.val = 100001;
                head = head.next;
            }
            return null;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}